package leetcode每日一题.leetcode20212.滑动窗口;

/**
 * 1. 问题描述
 *      给你一个整数数组nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，
 *      然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
 *      如果可以将x恰好减到0，返回最小操作数；否则，返回 -1 。
 *
 * 2. 算法分析
 *      此题直接套用滑动窗口算法无法实现，我们需要将此题转化为滑动窗口的类型，
 *      题目的要求是不断移除数组的端点元素，知道x减少为0，换个方向，我们先求
 *      出数组的总和sum，然后sum-x，那么整个题就转化为sumx-x最大的连续子数组
 *      (即本质上将端点问题转化为端点的中间的问题了，这样就是一个连续的子数组
 *      ，从而可以使用滑动窗口实现)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q001_将x减到0的最小操作数 {

    /**
     * 滑动窗口   注意转化的思路
     * @param nums
     * @param x
     * @return
     */
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        if(n == 0 || nums == null) {
            return -1;
        }
        int sum = 0; // 记录数组的总和
        for(int i = 0; i < n; i++) {
            sum += nums[i];
        }
        int target = sum - x; // 目标值
        // 我们的目的就是：找到尽可能最长的连续子数组使得其和为target
        int left = 0; // 定义左窗口
        int right = 0; // 定义右窗口
        int temp = 0; // 临时变量，记录当前窗口的总和
        int res = -1; // 记录全局最长连续子数组长度
        while(right < n) {
            temp += nums[right];
            right++;
            while(temp > target) { // 如果当前temp大于target
                if(left >= n) {
                    break;
                }
                temp -= nums[left];
                left++;
            }
            if(temp == target) {
                res = Math.max(res,right - left);
            }
        }
        return res == -1 ? -1 : n - res;
    }
}
